import java.util.LinkedList;
import java.util.Queue;

class Solution542 {
    public int[][] updateMatrix(int[][] mat) {
       
       int m = mat.length , n = mat[0].length ;
       int[][] sum = new int[m][n] ; 
       boolean[][] hash = new boolean[m][n] ; 
       Queue<int[]> queue = new LinkedList<>() ;
       for(int i=0 ;i < m ;i ++){
        for(int j=0 ; j < n ; j++){
         if(mat[i][j] == 0){
            queue.add(new int[]{i , j}) ; 
            hash[i][j] = true ;
         }
        }
       }
       int[] dx = {0,0,1,-1} ; 
       int[] dy = {1,-1,0,0} ; 
       int len =  0 ;
       
       while(!queue.isEmpty()){
         len ++ ;
         int  size = queue.size() ;
         for(int i=0 ; i < size ; i ++){
             int[] arr = queue.poll() ;
             int a = arr[0] , b = arr[1] ; 
             for(int j=0 ; j < 4 ; j ++){
                int x = a+dx[j] , y = b+dy[j] ; 
                if(x >=0 && x < m && y>=0 && y < n && hash[x][y]==false ){
                    hash[x][y] = true ;
                    sum[x][y] = len ; 
                    queue.add(new int[]{x , y}) ; 
                }
             }

         }


       }

        return sum ;
    }
}